package dp;

public class _14_518_零钱兑换Ⅱ {
    public static int change(int amount, int[] coins) {
    	// 求组合总数的递推公式：dp[j] += dp[j-coins[i]];
    	// coins表示有不同金额的硬币，硬币可重复使用
    	// amount表示需要凑成的金额
    	// 计算能凑出amount的硬币组合的总数
    	int dp[] = new int[amount+1];
    	dp[0] = 1;
    	for(int i = 0; i < coins.length; i++) { // 物品
    		for(int j = coins[i]; j <= amount; j++) { // 容量
				dp[j] += dp[j-coins[i]];
    		}
    	}
    	
    	return dp[amount];
    }
    
    public static void main(String[] args) {
		int coins[] = {1,2,5};
		System.out.println(change(5,coins));
	}
}
